--- Day 9: All in a Single Night --- Every year, Santa manages to deliver all of his presents in a single night. This year, however, he has some new locations to visit; his elves have provided him the distances between every pair of locations. He can start and end at any two (different) locations he wants, but he must visit each location exactly once. What is the shortest distance he can travel to achieve this? For example, given the following distances: London to Dublin = 464 London to Belfast = 518 Dublin to Belfast = 141 The possible routes are therefore: Dublin -> London -> Belfast = 982 London -> Dublin -> Belfast = 605 London -> Belfast -> Dublin = 659 Dublin -> Belfast -> London = 659 Belfast -> Dublin -> London = 605 Belfast -> London -> Dublin = 982 The shortest of these is London -> Dublin -> Belfast = 605, and so the answer is 605 in this example. What is the distance of the shortest route?



In [21]:

    
import re
import itertools
from collections import defaultdict

_PARSER = re.compile("([a-zA-Z]+) to ([a-zA-Z]+) = ([0-9]+)")

def load_distances(distances):    
    city_distances = defaultdict(dict)        
    for d in distances:
        c_from, c_to, kms = _PARSER.match(d.strip()).groups()
        city_distances[c_from][c_to] = kms
        city_distances[c_to][c_from] = kms
    return city_distances

def count_distance(distances, route):
    p = route[0]
    kms = 0
    for c in route[1:]:
        kms += int(distances[p][c])
        p = c
    return kms

def find_route(distances, shortest=True):
    city_distances = load_distances(distances)
    all_cities = list(city_distances.keys())
    
    min_route = tuple(all_cities)
    min_distance = count_distance(city_distances, min_route)
    
    for route in itertools.permutations(city_distances.keys()):
        kms = count_distance(city_distances, route)
        if (shortest and kms < min_distance) or (not shortest and kms > min_distance):
            min_route = route
            min_distance = kms
            
    return min_route, min_distance



In [22]:

    
%%time

# Test example
example = ["London to Dublin = 464","London to Belfast = 518","Dublin to Belfast = 141"]
print(find_route(example))









    



(('Belfast', 'Dublin', 'London'), 605)
CPU times: user 148 µs, sys: 8 µs, total: 156 µs
Wall time: 164 µs



In [23]:

    
%%time

# Check input
with open('day9/input.txt', 'rt') as fd:
    print(find_route(fd))









    



(('Norrath', 'Faerun', 'Straylight', 'Tristram', 'AlphaCentauri', 'Snowdin', 'Arbre', 'Tambi'), 251)
CPU times: user 398 ms, sys: 180 µs, total: 398 ms
Wall time: 397 ms

--- Part Two --- The next year, just to show off, Santa decides to take the route with the longest distance instead. He can still start and end at any two (different) locations he wants, and he still must visit each location exactly once. For example, given the distances above, the longest route would be 982 via (for example) Dublin -> London -> Belfast. What is the distance of the longest route?



In [24]:

    
%%time

# Test example
example = ["London to Dublin = 464","London to Belfast = 518","Dublin to Belfast = 141"]
print(find_route(example, shortest=False))









    



(('Belfast', 'London', 'Dublin'), 982)
CPU times: user 237 µs, sys: 11 µs, total: 248 µs
Wall time: 261 µs



In [25]:

    
%%time

# Check input
with open('day9/input.txt', 'rt') as fd:
    print(find_route(fd, shortest=False))









    



(('Snowdin', 'Tambi', 'Norrath', 'AlphaCentauri', 'Straylight', 'Arbre', 'Faerun', 'Tristram'), 898)
CPU times: user 404 ms, sys: 0 ns, total: 404 ms
Wall time: 404 ms



In [ ]: